package com.list88zhu.android.sunflower.algorithm;

import android.app.ActivityManager;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <pre><code>
 *
 *  </code></pre>
 *
 * @author zhuyingming@qmtv.com
 * @date 2018/9/14
 */
public class Algorithm {

    private static int[] mArray = {5, 1, 9, 7, 0, 2, 4, 6, 3, 8};

    public static void main(String[] args) {
//        mergeSort(mArray, 0, mArray.length-1, new int[mArray.length]);
//        printArray(mArray);

//        String s = new String("abc");
//        String s1 = "abc";
//        String s2 = new String("abc");
//        System.out.println(s == s1.intern());
//        System.out.println(s == s2.intern());
//        System.out.println(s1 == s2.intern());

        String a = "abc";
        String b = "abc";
        System.out.println(a == b);
        System.out.println(a.equals(b));
    }


    /**
     * 一、冒泡排序：
     *
     * 一次列表遍历，每相邻的两个数比较，前者比后者大，则交换，最后列表中最大的一个数被移到最后
     * 在剩下的列表中再次步骤一，如此往复直到列表有序
     */
    public static void bubbleSort(int[] array) {
        final int size = array.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }

    /**
     * 二、选择排序：
     *
     * 第一次遍历，找出最小的数，然后和第一个数交换
     * 在剩下的列表中，重复第一步，直到列表有序
     */
    public static void selectSort(int[] array) {
        int size = array.length;
        for (int i = 0; i < size; i++) {
            int index = size - 1;
            for (int j = size - 1; j > i; j--) {
                if (array[j - 1] < array[index]) {
                    index = j - 1;
                }
            }
            int temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
    }

    /**
     * 三、快速排序
     */
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int middle = getMiddle(array, low, high);
            quickSort(array, low, middle - 1);
            quickSort(array, middle + 1, high);
        }
    }

    private static int getMiddle(int[] array, int low, int high) {

        final int flag = array[low];
        while (low < high) {
            while (low < high && array[high] > flag) {
                high--;
            }
            array[low] = array[high];

            while (low < high && array[low] < flag) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = flag;
        return low;

    }

    /**
     * 四、插入排序
     * 基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适
     * 位置后），直到全部插入排序完为止。
     */
    public static void insertSort(int[] array) {
        final int size = array.length;
        for (int i = 1; i < size; i++) {
            int temp = array[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
                if (array[j] > temp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
    }


    public static void shellSort2(int[] array) {
        final int size = array.length;
        for(int i = size/2; i >= 1; i = i/2){
            int gap = i;
            for(int j = gap; j < size; j++) {
                int num = array[j];
                int k;
                for(k = gap; k >= 0; k -= gap){
                    if(array[k] > array[j]) {
                        array[j] = array[k];
                    }else{
                        break;
                    }
                }
                array[k] = num;
            }
        }
    }


    /**
     * 归并排序
     * @param array
     * @param left
     * @param right
     * @param temp
     */
    public static void mergeSort(int[] array, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right)/2;
            mergeSort(array, left, mid, temp);
            mergeSort(array, mid+1, right, temp);
            merge(array, left, mid, right, temp);
        }
    }

    private static void merge(int[] array, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while(i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[t++] = array[i++];
            }else{
                temp[t++] = array[j++];
            }
        }
        while(i <= mid) {
            temp[t++] = array[i++];
        }
        while (j <= right) {
            temp[t++] = array[j++];
        }
        t = 0;
        while (left <= right) {
            array[left++] = temp[t++];
        }
    }


    private static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
        }
        System.out.println();
    }
}
